package com.example.question.bt.backtrack2;

import java.util.ArrayList;
import java.util.List;

public class Code02_131 {
    public static void main(String[] args) {
        Code02_131 code = new Code02_131();
        boolean aa = code.isPalindrome("aa");
        System.out.println(aa);
        System.out.println("code.partition(\"aab\") = " + code.partition("aab"));
    }

    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if (s == null || s.length() < 1) {
            return result;
        }
        findPartition(s, 0, new ArrayList<>(), result);
        return result;
    }


    private void findPartition(String s, int startIndex, List<String> paths, List<List<String>> result) {
        // 边界条件
        if (startIndex == s.length()) {
            result.add(new ArrayList<>(paths));
            return;
        }

        for (int len = 1; len < s.length(); len++) {
            if (startIndex + len <= s.length()) {
                String str = s.substring(startIndex, startIndex + len);
                if (isPalindrome(str)) {
                    paths.add(str);
                    findPartition(s, startIndex + len, paths, result);
                    paths.remove(paths.size() - 1);
                }
            }
        }
    }

    private boolean isPalindrome(String str) {
        char[] chars = str.toCharArray();
        int left = 0;
        int right = chars.length - 1;
        if (left > right) {
            return false;
        }
        while (right >= left) {
            if (chars[left] != chars[right]) {
                return false;
            }
            left += 1;
            right -= 1;
        }
        return true;
    }
}
